package com.itzmn.datastructure.newcode;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/31 13:22
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 归并排序
 *
 *
 */
public class MergeSort {


    public static void main(String[] args) {
        new MergeSort().init();
    }

    private void init() {
        int[] ints = {3, 4, 2, 5, 7, 6};
        getsum(ints);
        for (int i=0;i<ints.length;i++){
            System.out.print(ints[i]+" ");
        }
    }

    private int getsum(int[] arr){

        sort(arr,0,arr.length-1);

        return 0;
    }


    /**
     *  将数组划分多个部分。
     * @param arr 数组
     * @param L 数组左边界
     * @param R 数组右边界
     */
    public void sort(int[] arr,int L,int R){

        if (L == R){
            return;
        }
        int mid = (L + R) /2 ;

        sort(arr,L,mid);
        sort(arr,mid+1,R);

        // 合并两个数组
        merge(arr,L,R,mid);

    }

    /**
     * 将分开的数组合并
     */
    public void merge(int[] arr,int L,int R,int mid){

        int[] help = new int[R - L + 1];

        int i = L,j=mid+1,k=0;

        while (i<=mid && j<=R){

            help[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];

        }

        while (i <= mid){
            help[k++] = arr[i++];
        }
        while (j <= R){
            help[k++] = arr[j++];
        }


        for (int m=0;m<help.length;m++){
            arr[L++] = help[m];
        }

    }

}
